package h_10_22;

import java.util.HashMap;

/**
 * 3679. 使库存平衡的最少丢弃次数
 * https://leetcode.cn/problems/minimum-discards-to-balance-inventory/description/
 */
public class Main3 {
    /**
     * 优化
     * @param arrivals
     * @param w
     * @param m
     * @return
     */
    public int minArrivalsToDiscard(int[] arrivals, int w, int m) {
        int n = arrivals.length;
        HashMap<Integer,Integer> hash = new HashMap<>();
        int ret = 0;
        for(int i = 0;i < n;i++) {
            int x = arrivals[i];
            int count = hash.getOrDefault(x,0);
            if(count == m) {
                // 这里直接将这个值进行丢弃，赋值为0，之后次数+1
                arrivals[i] = 0;
                ret++;
            }else {
                hash.put(x,count + 1);
            }

            // 判断是否出窗口
            int left = i - w + 1;
            if(left >= 0) {
                hash.put(arrivals[left],hash.getOrDefault(arrivals[left],0) - 1);
            }
        }
        return ret;
    }

    /**
     * 笨重
     * @param arrivals
     * @param w
     * @param m
     * @return
     */
    public int minArrivalsToDiscard2(int[] arrivals, int w, int m) {
        int n = arrivals.length;
        HashMap<Integer,Integer> hash = new HashMap<>();
        int count = 0;
        int ret = 0;
        for(int i = 0;i < n;i++) {
            hash.put(arrivals[i],hash.getOrDefault(arrivals[i],0) + 1);
            if(hash.get(arrivals[i]) > count) {
                count = hash.get(arrivals[i]);
            }

            if(count > m) {
                // 不符合抛弃
                hash.put(arrivals[i],hash.get(arrivals[i]) - 1);
                count--;
                arrivals[i] = 0;
                ret++;
            }

            if(i < w - 1) {
                continue;
            }

            // 出窗口
            if(hash.getOrDefault(arrivals[i - w + 1],0) == count) {
                count--;
            }
            hash.put(arrivals[i - w + 1],hash.getOrDefault(arrivals[i - w + 1],0) - 1);
        }
        return ret;
    }
}
